# -*- coding:utf-8 -*-
'''
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
使用辅助栈递归中序便利后把栈中元素左右连接成双向
中序遍历一波然后改变左右指向就ok了
'''
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:return
        self.arr = []
        self.midTraversal(pRootOfTree)
        for i,v in enumerate(self.arr[:-1]):
            v.right = self.arr[i + 1]
            self.arr[i + 1].left = v
        return self.arr[0]
    def midTraversal(self, root):
        if not root: return
        self.midTraversal(root.left)
        self.arr.append(root)
        self.midTraversal(root.right)


node_4 = TreeNode(4)
node_8 = TreeNode(8)
node_6 = TreeNode(6)
node_12 = TreeNode(12)
node_16 = TreeNode(16)
node_14 = TreeNode(14)
node_10 = TreeNode(10)
node_6.left = node_4
node_6.right = node_8
node_10.left = node_6
node_14.left = node_12
node_14.right = node_16
node_10.right = node_14

s = Solution()
a = s.Convert(node_10)
print(a)